The invention relates generally to communications networks and more particularly to a system and a method for routing data through multiple network nodes.
Various communications systems require routing of voice and data packets, blocks, frames or cells (collectively referred to herein as xe2x80x9cpacketsxe2x80x9d) through two or more network nodes via communication links to provide connectivity between sites that are located at different networks. In a sophisticated communications system, the nodes that provide the connectivity between the networks operate using a routing algorithm that allows prioritization of packets that are relayed through the nodes. For example, voice packets are typically placed ahead of data packets because the voice packets carry real-time information.
In addition to prioritization of packets, the nodes may be configured to monitor the topology of the system, including the status of the communication links. The link status information may include the operational state and the remaining available bandwidth for each communication link in the system. Using the link status information, the nodes compute routing paths to establish new connections. A reservation protocol may be utilized by the nodes to reserve bandwidth on one or more communication links that define the computed routing paths. Such reservation protocol may be necessary to guarantee space on each communication link along the routing paths. The computed routing paths may vary depending on routing parameters that are being utilized by a particular node. The routing parameters may include the number of hops, the amount of toll charge associated with the path, and the distance between the two connecting nodes.
In a normal packet traffic condition, the path chosen by a source node (i.e., the network node associated with a connection-originating network) may be the optimal path in accordance with the prescribed routing parameters. However, when a communication link in the optimal path is over-crowded with reservations of established connections, the source node may be forced to route the new connection through a less preferred path. A concern is that bandwidth of the over-crowded communication link may be depleted due to a number of low priority connections that have been previously routed through the now over-crowded communication link. The problem arises when the pending connection to be made is a high priority connection, such as a connection for voice data transmission. The connectivity resources of the system are not being utilized efficiently when the high priority connection must be routed through a less preferred path, because the optimal path is being utilized by the lower priority connections.
The problem will be further described with reference to FIG. 1. In FIG. 1, a prior art communications system 10 having networks 12, 14, 16 and 18 is shown. The networks 12-18 are illustrated as local area networks (LANs). However, the networks 12-18 can be other types of network, such as wide area networks (WANs) or metropolitan area networks (MANs). Each LAN 12-18 can support a number of sites that may be physically located in a confined area, such as an office building, a building complex or a campus. For simplification, only the LANs 12 and 18 are shown with a number of associated sites. The LAN 12 includes sites 20, 22 and 24. The LAN 18 includes sites 26, 28 and 30. At each site 20-30, a computer 32 and/or a telephone 34 may be connected to their respective network.
The LANs 12-18 are interconnected by communication links 36, 38, 40 and 42. The communication links 36, 38, 40 and 42 may be in a form of physical communication links, such as fiber optic cables, or in a form of wireless communication links. The communication links 36-42 provide connectivity between nodes 44, 46, 48 and 50. The communication link 36 connects the node 44 to the node 46. The communication link 38 connects the node 44 to the node 50. The communication link 40 connects the node 46 to the node 50. The communication link 42 connects the node 48 to the node 50. The nodes 44-50 may be gateways, switches or routers having prioritizing and routing capabilities. However, the nodes 44-50 are identified in FIG. 1 as routers. Each router 44-50 is associated with one of the LANs 12, 14, 16 and 18. The router 44 is associated with the LAN 12, while the router 46 is associated with the LAN 14. The router 48 is associated with the LAN 16, whereas the router 50 is associated with the LAN 18.
The above-described problem may arise in the following manner. Initially, the packet traffic on the communication links 36-42 is light and much of the bandwidth on each of the links is available. One of the sites at LAN 12, for example the site 20, may request a data connection to another site at LAN 18, for example the site 26. Assuming that the optimal path for the data connection from LAN 12 to LAN 18 is through the communication link 38, the router 44 responds to the request by reserving the required bandwidth on the communication link 38. As additional data connections are made through the communication link 38, the available bandwidth on the communication link 38 may be down to 5% of its capacity. The established connections through the communication link 38 may include many data connections that have a lower priority than voice connections. At such time, a site at LAN 12, for example the site 24, requests a voice connection to a site at LAN 18, for example the site 28. This voice connection requires 10% of the total bandwidth of the communication link 38. When this request is received by the router 44, the router 44 has no choice except to route the voice connection through the communication links 36 and 40 via the router 46 due to lack of sufficient bandwidth remaining on the communication link 38, even though the optimal path is through the communication link 38.
The compulsory routing of the voice connection through the router 46 can have a negative effect on the packet traffic at the router 46. Since the voice connection has a high priority, the router 46 must relay the packets of the voice connection ahead of lower priority packets that are being transmitted through the established connections via the router 46. The newly introduced voice connection may cause congestion and may increase the probability of dropped packets at the router 46. In addition, the conventional routing technique inefficiently utilizes the connectivity resources of the system 10, since the high priority connection is routed through the less preferred path, while the optimal path for the high priority connection is occupied by the lower priority connections.
What is needed is a communications system and a method that can efficiently utilize the connectivity resources of the system to provide the best possible paths for connections according to the priority status of the connections, regardless of the order that the connections were established.
In accordance with the present invention, a network node and a method of dynamically reconfiguring routes of established connections in a communications system operate to provide the optimal path for a new connection based on a priority status of the new connection. The optimal path is provided even when a communication link along the optimal path does not have a sufficient amount of available bandwidth to accommodate the new connection. The network node operates in conjunction with other network nodes in the system to reroute one or more established connections that have reserved bandwidth on a communication link on the optimal route and have a lower priority status than the new connection, thereby increasing the available bandwidth on the communication link to accommodate the new connection. The network node also performs conventional functions of a router. Therefore, the network node will be referred to as an xe2x80x9cenhanced router.xe2x80x9d The enhanced router and the method can be implemented in any communications system in which information is transmitted in packets, blocks, frames or cells (collectively referred herein as xe2x80x9cpacketsxe2x80x9d).
In the preferred embodiment, the enhanced router operates to monitor the status of communication links in the system by exchanging the status information with other network nodes. The link status includes the available bandwidth on the communication links and the priority status of each presently established connection that is routed through at least one of the communication links. Preferably, every network node in the system is an enhanced router. A network monitor within the enhanced router keeps track of the link status of communication links that are coupled to the enhanced router by recording information regarding new connections that have been routed by the enhanced router and regarding termination of established connections that had been routed through the enhanced router. The network monitor shares the link status information with network monitors of other enhanced routers throughout the system to monitor the current status of every communication link. The link status information is utilized by the enhanced routers to perform the rerouting operation.
When a request signal for a new connection is received at the enhanced router from an associated network, such as a local area network (LAN), a central processing unit (CPU) of the enhanced router computes the optimal path for the new connection using a routing protocol that is stored in memory. The request signal includes information regarding the required bandwidth for the new connection and the priority status of the new connection. The CPU determines the priority status of the new connection by utilizing a prioritization protocol that is also stored in memory. The enhanced router associated with the originating network of the new connection will be referred to as the xe2x80x9csource enhanced router.xe2x80x9d The enhanced router associated with the terminating network of the new connections will be referred to as the xe2x80x9cdestination enhanced router.xe2x80x9d The optimal path is the best course from the source enhanced router to the destination enhanced router through one or more communication links in accordance with prescribed routing parameters. The routing parameters may include the number of hops, the amount of toll charge associated with the path, and the distance between the two connecting enhanced routers.
Using the link status information provided by the network monitor, the CPU of the source enhanced router determines whether a sufficient amount of available bandwidth exists on each communication link on the optimal route to accommodate the new connection. If a particular communication link on the optimal route does not have the sufficient amount of available bandwidth, the CPU determines whether there are established connections having a lower priority status than the new connection. The particular communication link will be referred to as the xe2x80x9ctarget linkxe2x80x9d for clarity. If there are established connections having a lower priority status, the CPU determines whether removing one or more of these established connections from the target link will increase the available bandwidth on the target link sufficiently to accommodate the new connection.
After a positive determination that removing one of more of the established connections will accommodate the new connection, the source enhanced router operates to reroute one of the established connections through an alternate path to bypass the target link. In one embodiment, a reroute-signal generator of the source enhanced router transmits reroute signals to the end enhanced routers, i.e., the source and destination enhanced routers of the established connection that is to be rerouted. The end enhanced routers then transmit acknowledgment signals to the source enhanced router for confirmation, utilizing their respective reroute-signal generators. Next, one of the end enhanced routers, e.g., the destination enhanced router of the established connection, transmits reservation signals using a reservation unit to every enhanced router on the alternate path to reserve bandwidth on all of the communication links on the alternate path. The end enhanced routers then terminate the established connection and re-establish the established connection through the alternate path, bypassing the target link. In a situation where the source enhanced router of the new connection is also one of the end enhanced routers, the source enhanced router will perform the functions that are associated with the source enhanced router and the end enhanced router.
In another embodiment, the source enhanced routers transmit the reroute signals to the enhanced routers that are located at the ends of the target link. These enhanced routers will be referred to as the Atarget routers. A The target routers then transmit acknowledgment signals to the source enhanced router in response to the reroute signals. In this embodiment, the target routers operate to redirect a portion of the established connection that is routed through the target link. This is accomplished by rerouting that portion through a secondary path from one target router to the other target router that bypasses the target link. Initially, one of the target routers transmits one or more reservation signals to the enhanced routers on the secondary path to reserve bandwidth on the communication links on the secondary path. Next, the portion of the established connection through the target link is terminated and connected through the secondary path. In a situation in which the source enhanced router is also one of the target routers, the source enhanced router will perform the functions that are associated with the source enhanced router and the target router.
The above procedure for removing an established connection from the target link may be repeated to remove additional established connections, if necessary, to increase the available bandwidth on the target link to accommodate the new connection. In addition, the entire process for removing one or more established connections from the target link may be repeated for other communication links on the optimal path, if necessary.
After all of the communication links on the optimal path have been prepared for the new connection, the source enhanced routers transmit reservation signals to every enhanced router on the optimal path to reserve bandwidth on the communication links on the optimal path for the new connection. Lastly, the new connection is established through the optimal path.